package cn.zhl.algorithm._3_并查集.common.impl;

import cn.zhl.algorithm._3_并查集.common.UnionFindCommon;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-06-12 16:30
 **/
public class UnionFindColl<V> extends UnionFindCommon<V> {

	public UnionFindColl(V[] vs) {
		super(vs);
	}
	/**
	* @Description: 根据目标值获取到对应node
	* @return:
	* @Author: 刘振华
	* @Date: 2020/6/12 16:47
	*/
	private Node<V> getNodeByDest(V v){
		Node<V> dest = nodes.get(v);
		if(dest == null) {
			throw new RuntimeException("找不到对应元素");
		}
		//查找并且同时做路径压缩
		while (dest.parent != dest){
			Node<V> parent = dest.parent;
			dest.parent = dest.parent.parent;
			dest = parent;
		}
		return dest;
	}

	@Override
	public V find(V v) {
		return getNodeByDest(v).value;
	}

	/**
	* @Description: 合并的时候比较rank的大小，相等的时候再维护rank
	* @Param:
	* @Param:
	* @return:
	* @Author: 刘振华
	* @Date: 2020/6/12 16:32
	*/
	@Override
	public void union(V v1, V v2) {
		Node<V> p1 = getNodeByDest(v1);
		Node<V> p2 = getNodeByDest(v2);
		if(p1.rank > p2.rank){
			p2.parent = p1;
		}else if(p1.rank < p2.rank){
			p1.parent = p2;
		}else{
			p1.parent = p2;
			p2.rank++;
		}
	}
}
